package main

import (
	"fmt"
)
type Node struct {
    Val  int
    Key  int
    Next *Node
    Prev *Node
}
 
var head *Node
var tail *Node
var nodeMap map[int]*Node
var cap int
 
func add(node *Node) {
    if head != nil {
        head.Prev = node
        node.Next = head
    }
    head = node
    if tail == nil {
        tail = node
    }
}
 
func remove(node *Node) {
    if node != head {
        node.Prev.Next = node.Next
    } else {
        head = node.Next
    }
    if node != tail && node.Next != nil {
        node.Next.Prev = node.Prev
    } else {
        if node.Prev != nil {
            tail = node.Prev
            tail.Next = nil 
        }
    }
}
 
func moveToFront(node *Node) {
    if node == head {
        return
    }
    if node == tail {
        if node.Prev != nil {
            tail = node.Prev
        }
    }
     
    if node.Prev != nil {
        node.Prev.Next = node.Next
        if node.Next != nil {
            node.Next.Prev = node.Prev
        }
    }
     
    node.Next = head
    head.Prev = node
    head = node
}
 
func get(key int) int{
    node, ok := nodeMap[key]
    if ok {
        moveToFront(node)
        return node.Val
    } else {
        return -1
    }
}
 
 
func set(key, value int) {
    node, ok := nodeMap[key]
    if ok {
        node.Val = value
        moveToFront(node)
    } else {
        node = &Node{Key: key, Val: value}
        add(node)
        nodeMap[key] = node
        if len(nodeMap) > cap {
            delete(nodeMap, tail.Key)
            remove(tail)
        }
    }
}
 
 
/**
 * lru design
 * @param operators int整型二维数组 the ops
 * @param k int整型 the k
 * @return int整型一维数组
 */
func LRU( operators [][]int ,  k int ) []int {
    // write code here
    var ret []int
    cap = k
    nodeMap = make(map[int]*Node)
    for _, ops := range operators {
        if ops[0] == 1 {
            set(ops[1], ops[2])
        } else {
            ret = append(ret, get(ops[1]))
        }
    }
    return ret
}


func main(){
	t:=[][]int{
		[]int{1,1,1},
		[]int{1,2,2},
		[]int{1,3,2},
		[]int{2,1},
		[]int{1,4,4},
		[]int{2,2},
	}
	fmt.Printf("%v\n",LRU(t,3))

}
